//双向链表
public class MyLinkedList implements IList{

    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        ListNode(int val){
            this.val=val;
        }
    }

    ListNode head;//链表的头
    ListNode last;//链表的尾

    @Override
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        if(head==null){
            head=last=node;
            return;
        }
//        ListNode curH=head;
//        curH.prev=node;
//        node.next=curH;
//        head=node;
        node.next = head;
        head.prev = node;
        head = node;
    }//头插就是头变尾不变

    @Override
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        if(head==null){
            head=last=node;
            return;
        }
        //尾插就是尾变头不变
        last.next=node;
        node.prev=last;
        last=node;
    }

    @Override
    public void addIndex(int index, int data) throws ListIndexOutOfBoundsException{
        int len=size();
        if(index<0||index>len){
            throw new ListIndexOutOfBoundsException("双向链表index位置不合法，index为："+index);
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==len){
            addLast(data);
            return;
        }
        ListNode node=new ListNode(data);
        ListNode cur=head;
        while(index>0){//找到下标为index的元素
            cur=cur.next;
            index--;
        }
        cur.prev.next=node;
        node.prev=cur.prev;
        node.next=cur;
        cur.prev=node;
    }

    @Override
    public boolean contains(int key) {
//        if(head==null){
//            return false;
//        }
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head!=null){
            ListNode cur=head;
            ListNode curNext=head.next;
            if(head.val==key){
                head.next.prev=null;
                head.next=null;
                //head.val=null;
                head=curNext;
                return;
            }else if(last.val==key){
                last.prev.next=null;
                last.prev=null;
                return;
            }else{
                while (cur!=null&&cur.val!=key){
                    cur=cur.next;
                }
                if(cur!=null){
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;
                    cur.next=null;
                    cur.prev=null;
                }
            }
        }
    }//我的代码没有办法对只有一个节点的情况进行删除--会出现空指针异常
    /*
    老师的代码：
    public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //是不是头节点
                if(cur == head) {
                    head = head.next;
                    if(head == null) {
                        //说明只有一个节点，且是头节点
                        last = null;
                        return;
                    }
                    head.prev = null;
                }else {
                    //删除尾节点
                    if(cur == last) {
                        last = last.prev;
                        last.next = null;
                    }else {
                        //删除中间节点
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else {
                cur = cur.next;
            }
        }
    }
     */

    @Override
    public void removeAllKey(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                if(cur==head){//删除头结点
                    head=head.next;
                    if(head==null){//开始的整个链表只有一个节点
                        last=null;
                        return;
                    }
                    head.prev=null;
                }else{
                    if(cur==last){//删除尾节点
                        last=last.prev;
                        last.next=null;
                    }else{//删除中间节点
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
            }
            cur=cur.next;
        }
    }

    @Override
    public int size() {
        int usedSize=0;//链表长度
        ListNode cur=head;
        while(cur!=null){
            usedSize++;
            cur=cur.next;
        }
        return usedSize;
    }

    @Override
    public void clear() {
        //head.next=null;不能简单地把head.next置为空，因为其他的引用关系还是存在，并没有被清空回收
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            //如果链表里的val为引用类型：head.val=null;
            cur.prev=null;
            cur.next=null;
            cur=curNext;
        }
        head=null;
        last=null;
    }

    @Override
    public void display() {
        //for(ListNode x:)
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
}

